Pencarian bagi mengantikan bot peluru berpandu kelas Sea Wolf yang telah usang, yang mula memasuki perkhidmatan pada tahun 1972, bermula pada pertengahan tahun 1990-an. Amerika Syarikat, Sweden dan Perancis terlibat di dalam persaingan bagi mendapatkan kontrak.[3] Pada bulan Mac 2000, Kementerian Pertahanan telah menganugerahkan kontrak kepada DCNS untuk mereka dan membina enam buah frigat. Antara ciri-ciri utama kontrak adalah persetujuan perpindahan teknologi. Di bawah perjanjian, DCNS akan mereka dan membina frigat pertama di limbungannya di Lorient, Perancis manakala lima buah selebihnya akan dibina oleh Singapore Technologies (ST) Marine di limbungan Benoi, Singapura. Penyelenggaraan dan padanan semula akan dilakukan oleh ST Marine.

Pembinaan Formidable bermula pada akhir 2002, apabila ia dibaringkan di Lorient pada bulan November 2002.